#include "linklist.h"

// 分割链表：根据基准值将链表分为三部分
void Partition(LinkList head, int pivot, 
               LinkList* less, LinkList* equal, LinkList* greater) {
    // less: 小于基准值的节点链表
    // equal: 等于基准值的节点链表  
    // greater: 大于基准值的节点链表
    LinkList lessHead = NULL, *lessTail = &lessHead;
    LinkList equalHead = NULL, *equalTail = &equalHead;
    LinkList greaterHead = NULL, *greaterTail = &greaterHead;
    
    while (head) {
        LinkList next = head->next;
        head->next = NULL;
        
        if (head->data < pivot) {
            *lessTail = head;
            lessTail = &(*lessTail)->next;
        } else if (head->data == pivot) {
            *equalTail = head;
            equalTail = &(*equalTail)->next;
        } else {
            *greaterTail = head;
            greaterTail = &(*greaterTail)->next;
        }
        head = next;
    }
    
    *less = lessHead;
    *equal = equalHead;
    *greater = greaterHead;
}

// 合并三个链表
LinkList MergeThreeLists(LinkList less, LinkList equal, LinkList greater) {
    LinkList head = NULL, *tail = &head;
    
    // 连接小于基准值的部分
    while (less) {
        *tail = less;
        less = less->next;
        tail = &(*tail)->next;
    }
    
    // 连接等于基准值的部分
    while (equal) {
        *tail = equal;
        equal = equal->next;
        tail = &(*tail)->next;
    }
    
    // 连接大于基准值的部分
    while (greater) {
        *tail = greater;
        greater = greater->next;
        tail = &(*tail)->next;
    }
    
    return head;
}

// 链表快速排序
LinkList QuickSort(LinkList head) {
    if (!head || !head->next) {
        return head;
    }
    
    // 选择第一个节点的值作为基准
    int pivot = head->data;
    
    // 分割链表
    LinkList less, equal, greater;
    Partition(head, pivot, &less, &equal, &greater);
    
    // 递归排序小于和大于基准值的部分
    less = QuickSort(less);
    greater = QuickSort(greater);
    
    // 合并结果
    return MergeThreeLists(less, equal, greater);
}

// 测试函数
void TestQuickSort() {
    int str[] = {5, 3, 8, 2, 1, 4, 7, 6, 9, 0};
    LinkList head = CreateList(str,10); // 带头结点
    printf("排序前: ");
    PrintList(head);

    // 排序（跳过头结点）
    head->next = QuickSort(head->next);

    printf("排序后: ");
    PrintList(head);
}

int main() {
    TestQuickSort();
    return 0;
}